Search for: All records

We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper: (i) We present a linear-size data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in O (( k +1)log 2 n ) time, where n is the current number of unit discs and k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc. (ii) We propose a linear-size data structure for maintaining the lower envelope of a set of x -monotone pseudo-lines. It can handle insertion/deletion of a pseudo-line in O (log 2 n ) time; for a query point x 0 ∈ ℝ, it can report, in O (log n ) time, the point on the lower envelope with x -coordinate x 0 ; and for a query point q ∈ ℝ 2 , it can return all k pseudo-lines lying below q in time O (log n + k log 2 n ). (iii) We present a linear-size data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc D , all input arcs intersecting D can be reported in O ( n 1/2+ɛ + k ) time, where k is the output size and ɛ > 0 is an arbitrarily small constant. A unit-circle arc can be inserted or deleted in O (log 2 n ) time. 

Abstract Impact-induced mixing between bolide and target is fundamental to the geochemical evolution of a growing planet, yet aside from local mixing due to jetting – associated with large angles of incidence between impacting surfaces – mixing during planetary impacts is poorly understood. Here we describe a dynamic instability of the surface between impacting materials, showing that a region of mixing grows between two media having even minimal initial topography. This additional cause of impact-induced mixing is related to Richtmyer-Meshkov instability (RMI), and results from pressure perturbations amplified by shock-wave refraction through the corrugated interface between impactor and target. However, unlike RMI, this new impact-induced instability appears even if the bodies are made of the same material. Hydrocode simulations illustrate the growth of this mixing zone for planetary impacts, and predict results suitable for experimental validation in the laboratory. This form of impact mixing may be relevant to the formation of stony-iron and other meteorites. 

We study a model of cheap talk with one substantive assumption: The sender's preferences are state independent. Our main observation is that such a sender gains credibility by degrading self‐serving information. Using this observation, we examine the sender's benefits from communication, assess the value of commitment, and explicitly solve for sender‐optimal equilibria in three examples. A key result is a geometric characterization of the value of cheap talk, described by the quasi concave envelope of the sender's value function. 

Protein misfolding is a recurring phenomenon that cells must manage; otherwise misfolded proteins can aggregate and become toxic should they persist. To counter this burden, cells have evolved protein quality control (PQC) mechanisms that manage misfolded proteins. Two classes of systems that function in PQC are chaperones that aid in protein folding and ubiquitin–protein ligases that ubiquitinate misfolded proteins for proteasomal degradation. How folding and degradative PQC systems interact and coordinate their respective functions is not yet fully understood. Previous studies of PQC degradation pathways in the endoplasmic reticulum and cytosol have led to the prevailing idea that these pathways require the activity of Hsp70 chaperones. Here, we find that involvement of the budding yeast Hsp70 chaperones Ssa1 and Ssa2 in nuclear PQC degradation varies with the substrate. In particular, nuclear PQC degradation mediated by the yeast ubiquitin–protein ligase San1 often involves Ssa1/Ssa2, but San1 substrate recognition and ubiquitination can proceed without these Hsp70 chaperone functions in vivo and in vitro. Our studies provide new insights into the variability of Hsp70 chaperone involvement with a nuclear PQC degradation pathway.